package leetcode

import (
	"container/heap"
	"sort"
)

/*
 * @lc app=leetcode.cn id=778 lang=golang
 *
 * [778] 水位上升的泳池中游泳
 */

// @lc code=start

type entry struct{ x, y, val int }
type hp []entry

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].val < h[j].val }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(x interface{}) { *h = append(*h, x.(entry)) }
func (h *hp) Pop() interface{} {
	old := *h
	n := len(old)
	ret := old[n-1]
	*h = old[0 : n-1]
	return ret
}

// 	小根堆（优先队列）
func swimInWater3(grid [][]int) int {
	n := len(grid)
	vis := make([][]bool, n)
	for i := range vis {
		vis[i] = make([]bool, n)
	}

	type pair struct{ x, y int }
	dirs := [4]pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	h := &hp{{0, 0, grid[0][0]}}
	vis[0][0] = true
	ret := 0
	for e := heap.Pop(h).(entry); e.x != n-1 || e.y != n-1; e = heap.Pop(h).(entry) {
		ret = max(ret, e.val)
		for _, p := range dirs {
			x, y := e.x+p.x, e.y+p.y
			if 0 <= x && x < n && 0 <= y && y < n && !vis[x][y] {
				vis[x][y] = true
				heap.Push(h, entry{x, y, grid[x][y]})
			}
		}
	}
	return max(ret, grid[n-1][n-1])
}

// 二分查找 + 小根堆
func swimInWater4(grid [][]int) int {
	n := len(grid)

	search := func(t int) bool {
		if grid[0][0] > t {
			return false
		}

		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, n)
		}

		type pair struct{ x, y int }
		dirs := [4]pair{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
		h := &hp{entry{0, 0, grid[0][0]}}
		vis[0][0] = true
		for h.Len() > 0 {
			e := heap.Pop(h).(entry)
			if e.x == n-1 && e.y == n-1 {
				return true
			}
			for _, p := range dirs {
				x, y := e.x+p.x, e.y+p.y
				if 0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && grid[x][y] <= t {
					vis[x][y] = true
					heap.Push(h, entry{x, y, grid[x][y]})
				}
			}
		}
		return false
	}

	return sort.Search(n*n-1, search)
}

// 二分查找
func swimInWater2(grid [][]int) int {
	n := len(grid)

	search := func(t int) bool {
		if grid[0][0] > t {
			return false
		}

		vis := make([][]bool, n)
		for i := range vis {
			vis[i] = make([]bool, n)
		}

		type pair struct{ x, y int }
		dirs := [4]pair{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
		h := []pair{{0, 0}}
		vis[0][0] = true
		for len(h) > 0 {
			e := h[0]
			h = h[1:]
			if e.x == n-1 && e.y == n-1 {
				return true
			}
			for _, p := range dirs {
				x, y := e.x+p.x, e.y+p.y
				if 0 <= x && x < n && 0 <= y && y < n && !vis[x][y] && grid[x][y] <= t {
					vis[x][y] = true
					h = append(h, pair{x, y})
				}
			}
		}
		return false
	}

	return sort.Search(n*n-1, search)
}

// 并查集：连通性问题
func swimInWater(grid [][]int) int {
	n := len(grid)

	pos := make([][2]int, n*n)
	for i, row := range grid {
		for j, h := range row {
			pos[h] = [2]int{i, j}
		}
	}

	dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	u := newUnionFind(n * n)
	for t := 0; ; t++ {
		p := pos[t]
		i, j := p[0], p[1]
		for _, d := range dirs {
			if x, y := i+d[0], j+d[1]; 0 <= x && x < n && 0 <= y && y < n && grid[x][y] < t {
				u.unite(i*n+j, x*n+y)
			}
		}
		if u.isSameRoot(0, n*n-1) {
			return t
		}
	}
}

// @lc code=end
